package com.atguigu.tree;

//二叉树
public class BinaryTreeDemo {
    Node root;

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    public static void main(String[] args) {
        BinaryTreeDemo binaryTreeDemo = new BinaryTreeDemo();
        Node node1 = new Node(1,"梨花");
        Node node2 = new Node(2,"菊花");
        Node node3 = new Node(3,"杏花");
        Node node4 = new Node(4,"桃花");
        Node node5 = new Node(5,"槐花");
        Node node6 = new Node(6,"花花");

        node1.setLeft(node2);
        node1.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setRight(node6);
        binaryTreeDemo.setRoot(node1);

//        System.out.println("前序遍历");
//        binaryTreeDemo.preOrder();
//        System.out.println("中序遍历");
//        binaryTreeDemo.midOrder();
//
//        System.out.println("后序遍历");
//        binaryTreeDemo.backOrder();

//        binaryTreeDemo.preFind(5);
//        binaryTreeDemo.midFind(5);
//        binaryTreeDemo.backFind(5);
        System.out.println("前序遍历");
        binaryTreeDemo.preOrder();
        binaryTreeDemo.delNo(5);
        System.out.println("前序遍历");
        binaryTreeDemo.preOrder();
    }

    public void preOrder(){
        this.root.preOrder();
    }

    public void midOrder(){
        this.root.midOrder();
    }

    public void backOrder(){
        this.root.backOrder();
    }

    public void preFind(int no){
        Node node = this.root.preFind(no);
        System.out.println(node);
    }

    public void midFind(int no){
        Node node = this.root.midFind(no);
        System.out.println(node);
    }

    public void backFind(int no){
        Node node = this.root.backFind(no);
        System.out.println(node);
    }

    public void delNo(int no){
        if (root != null ){
            if (root.getNo() == no){
                root = null;
            }else {
                root.delNo(no);
            }

        }else {
            System.out.println("root节点为null");
        }
    }
}

class Node {
    private int no;
    private String name;
    private Node left;
    private Node right;

    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //前序遍历
    public void preOrder(){
        System.out.println(this);
        //递归左边
        if (this.left != null){
            this.left.preOrder();
        }
        //递归右边
        if (this.right != null){
            this.right.preOrder();
        }

    }

    //中序遍历
    public void midOrder(){

        //递归左边
        if (this.left != null){
            this.left.midOrder();
        }
        System.out.println(this);
        //递归右边
        if (this.right != null){
            this.right.midOrder();
        }
    }

    //后序遍历
    public void backOrder(){
        //递归左边
        if (this.left != null){
            this.left.backOrder();
        }

        //递归右边
        if (this.right != null){
            this.right.backOrder();
        }

        System.out.println(this);
    }

    //前序查找
    public Node preFind(int no){
        Node temp = null;
        System.out.println("开始前序查找");
        if (no == this.no){
            temp = this;
            return temp;
        }

        //递归左边
        if (this.left != null){
            temp = this.left.preFind(no);
        }

        if (temp != null){
            return temp;
        }

        //递归右边
        if (this.right != null){
            temp = this.right.preFind(no);
        }

        if (temp != null){
            return temp;
        }

        return temp;
    }

    public Node midFind(int no){

        Node temp = null;

        //递归左边
        if (this.left != null){
            temp = this.left.midFind(no);
        }

        if (temp != null){
            return temp;
        }

        System.out.println("开始中序序查找");
        if (no == this.no){
            temp = this;
            return temp;
        }

        //递归右边
        if (this.right != null){
            temp = this.right.midFind(no);
        }

        if (temp != null){
            return temp;
        }

        return temp;
    }

    public Node backFind(int no){

        Node temp = null;

        //递归左边
        if (this.left != null){
            temp = this.left.backFind(no);
        }

        if (temp != null){
            return temp;
        }

        //递归右边
        if (this.right != null){
            temp = this.right.backFind(no);
        }

        if (temp != null){
            return temp;
        }

        System.out.println("开始后序查找");
        if (no == this.no){
            temp = this;
            return temp;
        }

        return temp;
    }

    //删除节点
    public void  delNo(int no){
        if (left != null && left.no == no){
            left = null;
            return;
        }

        if (right != null && right.no == no){
            right = null;
            return;
        }

        if (left != null){
            left.delNo(no);
        }

        if (right != null){
            right.delNo(no);
        }
    }

    public void setLeftNode(Node leftNode) {
        this.left = leftNode;
    }
}
